/**
 * 
 */
package leetCode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhong
 *
 */
public class SoupServings {

	Map<String, Double> res = new HashMap<>();

	public double soupServings(int N) {
		if (N > 5000) {
			return 1;
		}
		return getRes(N, N);
	}

	private double getRes(int n, int n2) {
		if (n == 0 && n2 == 0) {
			return 0.5;
		} else if (n == 0) {
			return 1;
		} else if (n2 == 0) {
			return 0;
		}
		String key = n + "_" + n2;
		System.out.println(key);
		if (res.containsKey(key)) {
			return res.get(key);
		}
		double r = 0.25 * (getRes(Math.max(n - 100, 0), n2) + getRes(Math.max(n - 75, 0), Math.max(n2 - 25, 0))
				+ getRes(Math.max(n - 50, 0), Math.max(n2 - 50, 0))
				+ getRes(Math.max(n - 25, 0), Math.max(n2 - 75, 0)));
		System.out.println(r);
		System.out.println("---------------------------");
		res.put(key, r);
		return r;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(new SoupServings().soupServings(660295675));
	}

}
